Generalization of telecommunication services have resulted in a rapid increase of demands for various communication services, for example, voice services, multimedia services, and Internet services requiring high data rates and communication quality through wired and wireless communication. Thus, it is important to develop physical layer technologies for providing high-rate transmission and reliable communication services to thereby satisfy such an increasing need of various users.
Among other various methods, a maximum likelihood (ML) detector satisfies the increasing need by simultaneously detecting a plurality of transmit symbols and providing optimal performance. However, the ML detector detects a transmit symbol that has a minimum Euclidean distance to a received signal from combinations of transmit symbols that can be transmitted, and accordingly, computational complexity of the ML detector exponentially increases according to the number of modulation levels and the number of transmit antennas. In particular, the computational complexity becomes severe because a detection process gets more complex when a large number of modulation levels is used and a great number of transmit antenna are used, and accordingly a use of the ML detector seems to be impossible.
Therefore, a sphere decoder is proposed to significantly reduce the computational complexity of the ML detector. In contrast to the ML detector, the search space of the sphere decoder is confined within a hypersphere with a given radius, centered at a received signal vector and the sphere decoder searches lattice vectors included inside the hypersphere, thereby reducing the complexity.
According to a sphere decoding method proposed by Viterbo (“A universal lattice code decoder for fading channels”, IEEE Trans. Inform. Theory, vol. 45, pp. 1639-1642, July, 1999), an initial radius can be chosen using noise variances. However, a valid lattice vector could not be included inside the hypersphere with high probability, resulting in a decoding failure. When no lattice vector is included inside the hypersphere, an erasure would be declared or the search process would be repeated with a larger initial radius. This method is more advantageous over other decoding methods because it has low probability of a decoding failure and an initial radius can be chosen using a fading coefficient to prevent an extremely large number of lattice vectors from being included inside the hypersphere due to deep fading in the channel. When the decoding fails, the decoding process is repeated with a larger initial radius.
However, this may also increase computational complexity because an extremely large number of lattice vectors may be included inside the hypersphere when using the larger initial radius. Further, it becomes difficult to substantially detect an ML estimate when the erasure is declared. Therefore, the sphere decoding method proposed by Viterbo may not achieve an exact ML performance. In addition, although the fading coefficient is taken into account under the deep channel fading, time consumed for the decoding process may not be significantly reduced due to the computational complexity.
On the other hand, Hassibi proposed a sphere decoding method (“On the expected complexity of sphere decoding”, Signals, Systems and Computers, 2001. Conference Record of the Thirty-Fifth Asilomar Conference, vol. 2, pp. 1051-1055 November 2001) to achieve the exact ML performance. According to Hassibi, a Euclidean distance is determined between a ZF estimate, called the Babai estimate, and a received signal, and therefore the ZF estimate and at least one lattice vector are included inside the hypersphere.
That is, since the ML detector searches the closest lattice vector to a received signal, this method guarantees the exact ML performance. However, the ZF estimate is quite far from the ML estimate in terms of the Euclidean distance and the initial radius is set too large, and therefore, an extremely large number of lattice vectors are still included inside the hypersphere, thereby increasing computational complexity of the sphere decoder.
Recently, a sphere decoding method with an improved radius search has been proposed by Zhao (“Sphere decoding algorithm with improved radius search”, IEEE Wireless Communications and Networking Conference 2004, vol. 4, pp. 2290-2294, March 2004.). According to this method, a statistical characteristic of noise power is taken into account when determining an initial radius. When an initial radius is too small to succeed in searching a lattice vector included inside a hypersphere with the initial radius, the initial radius is increased until at least one lattice vector is found inside the hypersphere in order to achieve the exact ML performance.
When searching a new lattice vector with the increased initial radius, information on newly searched lattice points are added and information on already searched lattice points remain as they are rather than being calculated again, thereby reducing a computation amount. In addition, an additional constraint is provided to reduce memory consumption for storing information. In addition, lattice point searching order in the conventional tree-pruning process is modified such that the searching starts from a lattice point closest to the center of the radius, thereby significantly reducing the complexity.
Operation time is estimated in order to prove reduction of the complexity when using the increased radius, however, analysis of the computation amount is performed with consideration of the probabilistic characteristic of noise power and the number of lattice points that increases as the initial radius increases. Therefore, it is difficult to estimate the substantial amount of computation required for operation of the sphere decoder. In addition, the number of lattice vectors included inside the hypersphere exponentially increases as the initial radius increases, and thus an extremely large number of lattice vectors may be included inside the hypersphere. As a result, the complexity greatly increases.
As described, the complexity of the sphere decoder greatly depends on an initial radius and a method for searching lattice vectors included inside a hypersphere. That is, an extremely large number of lattice points may be included inside the hypersphere and the complexity increases when the initial radius is set too large, whereas a valid lattice point may not exist inside the hypersphere and thus an ML estimate may not be obtained when the initial radius is set too small.
In addition, although an Euclidean distance between a minimum mean square error (MMSE) estimate or a zero forcing (ZF) estimate and a received signal is set as an initial radius so that a plurality of valid lattice vectors exist within a hypersphere with the initial radius, the complexity increases because the initial radius is still too large and too many lattice vectors are included inside the hypersphere.
The above information disclosed in this Background section is only for enhancement of understanding of the background of the invention and therefore it may contain information that does not form the prior art that is already known in this country to a person of ordinary skill in the art.